1. Technical Field
The present invention relates to a method and system for data processing in general and, in particular, to a method and system for extracting data for capacitance estimation. Still more particularly, the present invention relates to a method and system for shape processing within an integrated circuit layout for parasitic capacitance estimation.
2. Description of the Prior Art
During the course of designing a very large-scale integrated (VLSI) circuit, it is desirable to render some form of circuit characterization in order to determine the performance of the circuit. The characteristic of a VLSI circuit is generally dependent upon two major factors, namely, parasitic capacitance and parasitic resistance. Needless to say, parasitic capacitances associated with interconnect materials within a VLSI circuit can result in unacceptable circuit performances. Hence, it is very important to calculate all the parasitic capacitances within a VLSI circuit in order to determine whether or not they exceed certain design criteria before actual fabrication of the circuit.
Circuit characterization generally begins with circuit extraction. A circuit extraction software, such as a netlist extractor, is typically utilized to extract various circuits that are required to be simulated, from a VLSI circuit layout. The result of such circuit extraction includes not only the circuitry itself, but also includes the parasitic capacitance and parasitic resistance that are inherent within the interconnect materials. Within a circuit extraction software, there are shape-processing algorithms for detecting and reporting each capacitance event in the VLSI circuit layout. Because the amount of data within a VLSI circuit layout is very large, it is desirable for the data to be externalized, i.e., all the shapes in the VLSI circuit layout should not be loaded in the memory of a data processing system. A shape-processing algorithm known as "scanline" algorithm has this characteristic. Scanline algorithms have been utilized extensively in shape processing for design rule checking and parasitic capacitance (and resistance) extraction. In addition, several enhancements have been added to these scanline algorithms to achieve optimal run-times. Also, scanline algorithms only require an average of N.sup.1/2 shapes in the memory of the data processing system, where N is the total number of shapes in the layout. This invention is to provide further enhancements to these shape-processing algorithms for extracting interconnect information from a VLSI circuit layout according to a preferred data structure such that parasitic capacitance estimation can be performed in a more efficient manner.